1. Field of the Invention
The present invention relates to a least-recently-used (LRU) circuit which is used for identifying the priority order of data or data-storage areas to be replaced when storing those data newly loaded from main memory into a cache memory of a computer system. More particularly, the present invention relates to a least-recently-used circuit which allows cache memory to smoothly function even when the presence of an error may inhibit the priority order from correctly being identified.
2. Description of the Prior Art
A wide variety of computer systems extensively use cache memory for saving time in accessing memory. Cache memories store frequently accessible data from the main memory. In this case, controller system does not access the main memory first, but it accesses the cache memory. When accessible data is stored in the cache memory, the controller system directly accesses the accessible cache-hit data from the cache memory. Conversely, if no accessible data is stored in the cache memory, the controller system then transfers the accessible data from the main memory to the cache memory so that accessible data can be newly loaded to offset cache miss. Conventionally, the least-recently-used (LRU) algorithm, i.e., those data newly loaded from main memory, is stored in cache memory by replacing those data which were used in the furthest past.
FIG. 1 is the simplified block diagram of an LRU circuit when replacing data in the 4-bank set associative cache memory by applying the LRU algorithm cited above.
In the drawing, reference numeral 4 indicates four banks to be selected by the LRU control circuit 3, the LRU circuit 1 containing the LRU control circuit 3, which is a means for determining the replaceable object or renewing information in accordance with the content of LRU bit memory means 2 which is means for storing the recently-used relationship among these four banks.
Operation of the LRU circuit is described below.
When CPU (not shown) accesses the cache memory for reading data and then cache memory is hit by one of those four banks, the LRU circuit 1 transfers the content of LRU bit memory means 2 to the LRU control circuit 3 in order to renew memory content of LRU bit memory means 2, i.e., information representing which one of those four banks was accessed in the furthest past. Then, the LRU control circuit 3 renews the above information before allowing the renewed information to be written into LRU bit memory means 2.
On the other hand, if any cache miss occurs, the cache memory reads the accessible data delivered from the main memory (not shown) and internally loads it. The accessible data is then transferred to the data processor such as the CPU, and then, the cache memory stores this data. The LRU algorithm is used for determining which one of those four banks should store the new data, i.e., it determines replaceable data in any of those four banks. Concretely, when LRU circuit 1 transfers the content stored in LRU bit memory means 2 to the LRU control circuit 3, the LRU control circuit 3 selects any of these four replaceable banks in accordance with the LRU algorithm before storing those data newly read out of main memory into the selected bank. Simultaneously, the LRU control circuit 3 renews the content of data stored in the LRU bit memory means 2 and allows it to store the renewed content.
One example of the LRU control circuit using such an LRU algorithm is disclosed in the U.S. patent application Ser. No. 646,870, filed Aug. 31, 1984 (now abandoned).
Above-mentioned invention comprises "a first directing means which receives an access signal from each cache memory of the first pair of memories to decide the least-recently-used one between them and outputs a first access signal corresponding to receiving the access signal, a second directing means which receives an access signal from each cache memory of the second pair of memories to decide the least-recently-used one between them and outputs a second access signal corresponding to receiving the access signal, and a third directing means which receives said first and second signals from said first and second directing means to decide the least-recently-used one between said first and second pair of cache memories." That is, the aforementioned invention uses a tree construction, which requires many logical elements and is complicated. Processing speed is lowered because the processing result is obtained by tracing through the tree structure branch by branch.